MaxSliceSum solution
Task
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of
A[P] + A[P+1] + … + A[Q].Write a function:
int solution(vector<int> &A);that, given an array A consisting of N integers, returns the maximum sum of any slice of A.
For example, given array A such that:
A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0the function should return 5 because:
- (3, 4) is a slice of A that has sum 4,
- (2, 2) is a slice of A that has sum −6,
- (0, 1) is a slice of A that has sum 5,
- no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..1,000,000];
- each element of array A is an integer within the range [−1,000,000..1,000,000];
- the result will be an integer within the range [−2,147,483,648..2,147,483,647].
Solution
Just use the simple algorithm described in the attached documentation.
This is a special case of the Induction technique for solving problems.
This consists of asking:
- Given a solution for parameter x=k, can we easily construct a solution for parameter x=k+1?
- Can we find a solution for a trivial case like, x=0?
In this case, if we add the extra condition that the max slice should end at the end of the array, then given a solution for an array for N=k, the solution for N=k+1 is given by
soln(k+1) = max(A[k+1],soln(k)+A[k+1])The max slice without this condition is then obtained by calculating the maximim of the max slices for each ending position.
int solution(vector<int> &A){
int res= -1000001;// less than min value
int sliceMax=0;
for (int a : A){
// slice can’t be empty but it can contain only the last element
sliceMax= max(sliceMax+a,a);
res= max(res,sliceMax);
}
return res;
}Test Function
This code tests the solution
int main() {
vector<int> A0{3,2,-6,4,0};
assert(solution(A0) == 5);
vector<int> A9(1000000, 0);
assert(solution(A9) == 0);
vector<int> A2{-1000000};
assert(solution(A2) == -1000000);
vector<int> A1{1, 5};
assert(solution(A1) == 6);
vector<int> A7{1, 5, -2, 1};
assert(solution(A7) == 6);
vector<int> A6{1, 5, 2};
assert(solution(A6) == 8);
vector<int> A{1, -5, 2, -1, 4, 0};
assert(solution(A) == 5);
vector<int> A3{-1, -5, -2, -1, -4, 0, 0};
assert(solution(A3) == 0);
vector<int> A4{-1, -5, -2, -1, -4, -1, -1, 0};
assert(solution(A4) == 0);
vector<int> A8{1, 1000000, 0};
assert(solution(A8) == 1000001);
}Results
Codility Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N) |